public class Main {

    /**
     * 包含不超过两种字符的最长子串
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            //滑动窗口
//            char[] s = in.next().toCharArray();
//            int n = s.length;
//            int left = 0;
//            int right = 0;
//            int ret = 0;
//            int[] visi = new int[30];
//            int count = 0; //记录一下当前字符种类数
//            while (right < n) {
//                //入
//                if (visi[s[right] - 'a'] == 0) {
//                    //第一次入
//                    count++;
//                }
//                visi[s[right] - 'a']++;
//                while (count > 2) {
//                    //出窗口
//                    visi[s[left] - 'a']--;
//                    if (visi[s[left] - 'a'] == 0) { //有--->无
//                        count--;
//                    }
//                    left++;
//                }
//                //更新结果
//                ret = Math.max(ret, right - left + 1);
//                right++;
//            }
//            System.out.println(ret);
//        }
//    }


//    public class Solution {
//        ArrayList<String> ret;
//        int n;
//        char[] str;
//        boolean[] visi;
//        StringBuilder path = new StringBuilder();
//        public ArrayList<String> Permutation (String _str) {
//            str = _str.toCharArray();
//            Arrays.sort(str);
//            n = str.length;
//            visi = new boolean[n];
//            ret =  new ArrayList<>();
//            dfs(0);
//            return ret;
//        }
//        public void dfs(int pos) {
//            if (pos >= n) {
//                ret.add(path.toString());
//                return;
//            }
//            for (int i = 0; i < n; i++) {
//                if(visi[i] == true) continue;
//                if(i > 0 && !visi[i - 1] && str[i] == str[i - 1]) continue;
//                path.append(str[i]);
//                visi[i] = true;
//                dfs(pos +1);
//                visi[i] = false;//恢复现场
//                path.deleteCharAt(path.length() - 1);
//            }
//        }
//    }


    /**
     *
     * 求和
     *
     *
      */
  /*  import java.util.*;

    public class Main {
        public static int n;
        public static int m;
        public static boolean[] visi = new boolean[12];
        public static int sum = 0;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt();
            m = in.nextInt();
            dfs(1);
        }
        public static void dfs(int x) {
            if(sum == m) {
                for(int i = 1; i <= n; i++) {
                    if(visi[i] == true) {
                        System.out.print(i + " ");
                    }
                }
                System.out.println("");
                return;
            }
            //剪枝
            if(sum > m || x > n) {
                return;
            }
            //继续往下递归
            //选择下一个数
            sum += (x);
            visi[x] = true;
            dfs(x + 1);
            //恢复现场
            sum -= (x);
            visi[x] = false;
            //不选择下一个数
            dfs(x + 1);
        }
    }*/


/**
 * 提取不重复的整数
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            char[] s = (n + "").toCharArray();
//            int len = s.length;
//            HashSet<Character> hash = new HashSet<>();
//            StringBuilder ret = new StringBuilder();
//            for (int i = len - 1; i >= 0; i--) {
//                char cur = s[i];
//                if (!hash.contains(cur)) {
//                    ret.append(cur);
//                    hash.add(cur);
//                }
//            }
//            System.out.println(ret.toString());
//        }
//    }


/**
 * 哈夫曼编码
  */
//public class Main {
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int[] arr = new int[n + 1];
//        PriorityQueue<Long> heap = new PriorityQueue<>();
//        for (int i = 0; i < n; i++) {
//            heap.offer(in.nextLong());
//        }
//        long ret = 0;
//        while (heap.size() > 1) {
//            long a = heap.poll();
//            long b = heap.poll();
//            ret += (a + b);
//            heap.add(a + b);
//        }
//        System.out.println(ret);
//    }
//}


    /**
     * abb
     */
//public class Main {
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        char[] s = in.next().toCharArray();
//        long[] f = new long[27];//当前字符串中 _x子串出现的次数
//        long[] g = new long[27];//当前字符串中 每个字符同的个数
//        long ret = 0;
//        for(int i = 0; i < n; i++) {
//            //先跟新g表
//            char c = s[i];
//            ret += f[c - 'a'];
//            f[c - 'a'] = f[c - 'a'] + i - g[c - 'a'];//注意这个要放上面先跟新 因为 这个方程里面的g是要的0 - i-1 如果先更新了g 那g里面存的值就是0 - i 区间内的了 就不对了
//            g[c - 'a'] = g[c - 'a'] + 1;
//        }
//        System.out.println(ret);
//    }
//}

}
